package backtrack_or_fs.bfs_dfs;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    // 本题是典型的多源头bfs  和单bfs区别是 队列开始就有一系列点 而不是1个点
    // 技巧  使用grid[x][y] 是否等于 0 判断是否被访问过以及是否是陆地

    final int[][] moves = new int[][] {{1,0},{-1,0},{0,1},{0,-1}};
    public int maxDistance(int[][] grid) {
        int max = -1, n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j ++) {
                if(grid[i][j] == 1) {
                    queue.offer(new int[]{i, j}); // 也可使用状态压缩 比如 i* n + j  https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/yan-du-you-xian-bian-li-java-by-liweiwei1419/
                }
            }
        }

        if(queue.size() == 0 || queue.size() == n * n ) return -1; // 只有陆地或者海洋
        int[] cur = null;
        while(!queue.isEmpty()) {
            cur = queue.poll();
            for(int i = 0 ; i< 4 ;i++) {  // 遍历其他的海洋  遇到陆地或者被遍历过的海洋就跳过
                int nextX = cur[0] + moves[i][0];
                int nextY = cur[1] + moves[i][1];
                if( nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || grid[nextX][nextY] > 0) continue; // grid[nextX][nextY] > 0 表示陆地点或者是已经被其他到这个海洋点更近的陆地点bfs访问过   题目中 ： 这个海洋单元格到离它最近的陆地单元格的距离是最大
                grid[nextX][nextY] = grid[cur[0]][cur[1]] + 1; // 传播的过程 + 1
                queue.offer(new int[]{nextX, nextY});
            }

        }
        return grid[cur[0]][cur[1]] - 1;   // 距离包含了陆地的1
    }
}
class 地图分析_1162 {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    // 处理最近问题上 广度优先最合适
    // 广度优先、避免回搜因此针对每个点需要标记是否搜索过
    public int maxDistance(int[][] grid) {
        int maxMinDis = -1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 只看是海洋的点
                if (grid[i][j] == 0) {
                    maxMinDis = Math.max(maxMinDis, findNearestLand(i, j, grid));
                }
            }
        }
        return maxMinDis;
    }

    // 通过栈实现bfs   、   bfs点搜索注意不走已经走过的点  、  一样要剪枝
    private int findNearestLand(int x, int y, int[][] grid) {
        Deque<CurrentState> stack = new LinkedList<>();
        boolean[][] hadVisited = new boolean[grid.length][grid[0].length];
        stack.offer(new CurrentState(x, y, 0));
        while (!stack.isEmpty()) {
            CurrentState currentState = stack.poll();
            for (int i = 0; i < 4; i++) {
                int next_x = currentState.x + dx[i];
                int next_y = currentState.y + dy[i];
                // 以下两个if剪枝
                // 越界
                if (next_x < 0 || next_x > grid.length - 1 || next_y < 0 || next_y > grid[0].length - 1) {
                    continue;
                }
                // 避免走到下一个点又返回了
                if (hadVisited[next_x][next_y]) {
                    continue;
                } else {
                    hadVisited[next_x][next_y] = true;
                }
                if (grid[next_x][next_y] == 1) {
                    return currentState.distance + 1;
                }
                stack.offer(new CurrentState(next_x, next_y, currentState.distance + 1));
            }
        }
        return -1;
    }

    static class CurrentState {
        int x;
        int y;
        int distance;

        public CurrentState(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}